A topological sort provides a linear ordering of vertices such that for every directed edge from `u` to `v`, `u` comes before `v` in the ordering.

  • This is only possible on a Directed Acyclic Graph (DAG), as a cycle would create a circular dependency with no valid starting point.
  • The algorithm first runs a full DFS to calculate the finish time `f[v]` for every vertex `v`.
  • The finish time `f[v]` is the time when the DFS has finished exploring all descendants of `v`. A vertex that other vertices depend on will always have a later finish time.
  • The final topological sort is simply the list of vertices sorted in decreasing order of their finish times.
TOPO-ORDER(G):
  Run DFS to compute f[v] for all v
  Return vertices sorted by decreasing f[v]